package sort;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/15 11:10
 */
public class QuickSortPlus {
    public static void main(String[] args) {
        long[] array = {9, 3, 1, 5, 2, 4,45,-1, 3, 5, 6, 9, 8, 5, 3, 0, 1, 5};
        quickSort(array);
        System.out.println(Arrays.toString(array));

    }
    /**
     * 快速排序
     *
     * 时间复杂度：
     * 最好情况：O(n * log(n))
     * 平均情况：O(n * log(n))
     * 最坏情况：O(n^2)
     *
     * 空间复杂度：
     * 最好情况：O(log(n))
     * 平均情况：O(log(n))
     * 最坏情况：O(n)
     *
     * 稳定性：不具备稳定性
     * @param array
     */
    public static void quickSort(long[] array) {
        quickSortInternal(array, 0, array.length - 1);
    }

    private static void quickSortInternal(long[] array, int from, int to) {
        // 区间内的元素个数 <=16 时，插入排序最快
        int size = to - from + 1;
        if (size <= 16) {
            insertSort(array, from, to);
            return;
        }

        // 三数取中法，避免有序的情况时间复杂度高
        long leftValue = array[from];
        long rightValue = array[to];
        int midIdx = from + (to - from)/2;
        long midValue = array[midIdx];

        if (leftValue <= rightValue) {
            if (rightValue <= midValue) {
                // rightValue 作为基准值
            } else if (leftValue <= midValue) {
                // midValue
                swap(array, midIdx, to);
            } else {
                // leftValue
                swap(array, from, to);
            }
        } else {
            // leftValue > rightValue
            if (leftValue <= midValue) {
                // leftValue
                swap(array, from, to);
            } else if (midValue <= rightValue) {
                // rightValue
            } else {
                // midValue
                swap(array, midIdx, to);
            }
        }

        int i = partition(array, from, to);

        quickSortInternal(array, from, i - 1);
        quickSortInternal(array, i + 1, to);
    }

    private static int partitionPlus(long[] array, int from, int to) {
        long pivot = array[to];
        /*
        [from, b)  小于基准值
        [b, d)     等于基准值
        [d, g]     未比较的元素
        (g, to]    大于基准值
         */

        int b = from;
        int d = from;
        int g = to;

        // [d, g] 这个区间内没有元素时停止； d <= g 说明还有元素
        while (d <= g) {
            if (array[d] == pivot) {
                d++;
            } else if (array[d] < pivot) {
                swap(array, d, b);
                b++;
                d++;
            } else {
                // array[d] > pivot
                swap(array, d, g);
                g--;
            }
        }
        return d;
    }

    private static int partition(long[] array, int from, int to) {
       long pivot = array[to];
       int left = from;
       int right = to;
       while (left<right){
           while (left<right && array[left]<=pivot){
               left++;
           }

           array[right] = array[left];

           while (left<right && array[right]>= pivot){
               right--;
           }

           array[left] = array[right];
       }
       array[left] = pivot;
       return left;
    }

    private static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    private static void insertSort(long[] array, int from, int to) {
        int size = to - from + 1;
        for (int i = 1; i < size; i++) {
            // 有序区间 [from, from + i)
            // 无序区间的第一个元素的下标 [from + i]
            long x = array[from + i];

            // 遍历有序区间
            int j;
            for (j = from + i - 1; j >= from && array[j] > x; j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = x;
        }
    }
}